package leetcode_21_40;

public class divide_29 {
    /**
     * 被除数 dividend 和除数 divisor。
     * 将两数相除，要求 不使用 乘法、除法和取余运算。
     * 只能存储 32位整数 ，也就不能使用Long
     * X/Y
     *等价求Z     Z×Y≤ X<(Z+1)×Y
     * 在X到Y这个区间利用二分法查找符合条件的Z
     * 即找出最大的 Z 使得 Z×Y≥ X 成立
     *
     * 思路失败
     * 特殊数据太难处理了
     * @param dividend
     * @param divisor
     * @return
     */
    public static int divide(int dividend, int divisor) {
        // 考虑被除数为最小值的情况
        if (dividend == Integer.MIN_VALUE) {
            if (divisor == 1) {
                return Integer.MIN_VALUE;
            }
            if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
        }
        // 考虑除数为最小值的情况
        if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (dividend == 0) {
            return 0;
        }
        if(divisor==1) return dividend;
        if(divisor==-1) return -dividend;
        boolean isPlus = dividend > 0 && divisor > 0 || dividend < 0 && divisor < 0;   //判断结果正负
        //全部变为负数 Integer.MIN_VALUE 绝对值大于 Integer.MAX_VALUE ，就不用担心为正时溢出
        int Dividend=dividend< 0?dividend:-dividend,Divisor=divisor<0?divisor:-divisor;
        int l=1, r =Dividend==Integer.MIN_VALUE?Integer.MAX_VALUE: -Dividend >> 1,
                //防止被除数为Integer.MIN_VALUE转化为整数溢出
               //-Dividend >> 1减少运算
                ans=0;

        while (l <=  r){        //最大的 Z 使得 Z×Y≥ X 成立
            // 注意溢出，并且不能使用除法
            int mid = l + ((r- l) >> 1);
            int num=myPlus(  Divisor,mid );
              //结果应该为负数，变为正说明结果小于Integer.MIN_VALUE 溢出
            if(num>0)
                r=mid -1;
            else if(num>= Dividend){  //num 大于等于 Dividend
                ans=mid;
                l=mid+1;
            }else
                r=mid -1;
        }
        return isPlus?ans:-ans;
    }

    /**
     * 递归快速模拟乘法
     * 送进的数据一个负数一个正数
     * @param x
     * @param n
     * @return
     */
    public static int myPlus(int x, int n) {
        if (n == 0) return 0;
        int t=myPlus(x, n >> 1);// 这里是把这个递归操作抽取出来
        if(t>0)
            return 1;          //t>0 说明溢出了
        if ( n % 2 == 1 )     //每次变成奇数，都会少减或少加一次x
            return t+t+x;
        if(n % 2 == -1)
            return t+t-x;
        if(n == -1)
            return -x-x;    // 减两次自己
        return t + t;
    }

    /**
     * 学习别人思路
     * 想法一致，全部变为负数 Integer.MIN_VALUE 绝对值大于 Integer.MAX_VALUE ，就不用担心为正时溢出
     *一次次减是不可行的
     * 可以减除数的2倍,然后结果+2 , 4倍...... 故不停的左移除数, 直到其大于被除数的一半
     * 然后减去, 右移除数使其小于被除数,减去......依次类推, 直到被除数小于原始除数.
     * @param dividend
     * @param divisor
     * @return
     */
    public static int divide2(int dividend, int divisor) {
        boolean isPlus = (((dividend >>> 31) ^ (divisor >>> 31)) == 1);     //右移31位通过符号位判断结果正负
        if(dividend > 0) dividend = -dividend;  //变为负数
        if(divisor > 0) divisor = -divisor;
        int mod = divisor;                  //每次减去的值
        int minn = dividend >> 1;   //临界判断值就是dividend/2
        int now = 1;                          //记录当前减去的值是除数的多少倍，因为是负数，从-1开始
        while(mod >= minn) {          //将mod扩大到可以减去的最大值
            mod <<= 1;   //自乘2
            now <<= 1;    //跟随乘2
        }
        int ans = 0;
        while(dividend <= divisor){              //被除数小于原始除数终止
            while(mod < dividend){               //每次都让mod是当前被除数能减去除数2幂次方的最大值
                //因为是负数，所以这里是小于
                mod >>= 1;
                now >>= 1;
            }
            while(dividend <= mod) {            //减值，添加个数
                dividend -= mod;
                ans+=now;
            }
        }
        if(ans == -2147483648 && ! isPlus) return 2147483647;
        //结果是-2147483638且需要返回正数, 就说明溢出了, 返回2147483647
        return  isPlus?-ans:ans;
    }
}
